//选择排序

//选择排序就是每轮都选择位置i上的数为标准，让后面的数跟它比较
//每一轮外层排序后，最小的数都会被放到前面
//与冒泡排序不同的是，冒泡排序是在比较的过程中边比较边交换，而选择排序是在一轮的比较中记录下最小的数的下标，最后再进行一次交换

//时间复杂度O(n2)，空间复杂O(1)
//二元选择排序速度更快，但复杂度不变

import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] nums = new int[]{1,7,6,3,4,5,2};
//        selectionSort(nums);
        twosSelectionSort(nums);
        for(int i = 0 ; i < 7 ; i++){
            System.out.println(nums[i]);
        }
    }

    public static int[] selectionSort(int[] nums){

//        index记录每轮最小的数的下标位置，用于最后交换到i的位置上
        int index;
        for(int i = 0 ; i < nums.length - 1 ; i++){
            index = i ;
            for(int j = i+1 ; j < nums.length ; j++){
                if(nums[index] > nums[j]){
                    index = j;
                }
            }
            int tmp = nums[i];
            nums[i] = nums[index];
            nums[index] = tmp;
        }
        return nums;
    }

//    二元选择排序,既找最小值也找最大值
    public static int[] twosSelectionSort(int[] nums){

//        记录最大值和最小值的下标
        int minIndex, maxIndex;

            // i 只需要遍历一半
            for (int i = 0; i < nums.length / 2; i++) {
                minIndex = i;
                maxIndex = i;
                //因为要将最大值往后放，所以这里j的上限也在变化，不再是length。最大值放到后面以后就不再动这个位置
                for (int j = i + 1; j < nums.length - i; j++) {
                    if (nums[minIndex] > nums[j]) {
                        // 记录最小值的下标
                        minIndex = j;
                    }
                    if (nums[maxIndex] < nums[j]) {
                        // 记录最大值的下标
                        maxIndex = j;
                    }
                }

                // 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 nums[i] 相等，此时已经排序完成
                if (minIndex == maxIndex) break;

                // 将最小元素交换至首位
                int temp = nums[i];
                nums[i] = nums[minIndex];
                nums[minIndex] = temp;

                // 如果最大值的下标刚好是 i，由于 nums[i] 和 nums[minIndex] 已经交换了，现在minIndex位置上才是最大值，所以这里要更新 maxIndex 的值。
                if (maxIndex == i) maxIndex = minIndex;

                // 将最大元素交换至末尾
                int lastIndex = nums.length - 1 - i;
                temp = nums[lastIndex];
                nums[lastIndex] = nums[maxIndex];
                nums[maxIndex] = temp;
            }
            return nums;
    }
}
